class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 1 <= nums.length <= 200
        // 1 <= nums[i] <= 100
        // 题目要求如上，所以整个数组的最大和就是20000
        // 所以我们要开10001个空间大小的数组
        vector<int> dp(10001);

        int sum  = 0;
        for(auto &e : nums)
            sum += e;
        // 数组和是奇数，那么不可能可以分成两个等和的子集
        if(sum % 2 == 1)
            return false;

        // 我们要找的就是装满target，也就是一半的数组和的最大价值是否刚好等于target
        int target = sum / 2;

        // 先遍历物品，再遍历背包
        for(int i = 0; i < nums.size(); i++)
        {
            // 倒序遍历，确保每个元素只选了一次
            for(int j = target; j >= nums[i]; j--)
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        }

        // 这道题就是nums数组的元素即是重量，又是价值
        return dp[target] == target;
    }
};